/*! \file RBTree.inl
 *	\brief 
 *
 *	created:	2010/08/27
 *	created:	27:8:2010   16:58
 *	filename: 	C:\src\tactics-engine\libs\core\RBTree.inl
 *	file path:	C:\src\tactics-engine\libs\core
 *	file base:	RBTree
 *	file ext:	inl
 *	author:		Vitalii Trubchaninov
 *				venngraydog@gmail.com
 */

namespace tt{
namespace core{

template<typename Key, typename Data>
RBTree<Key, Data>::RBTree()
: m_root(NULL)
{

}

template<typename Key, typename Data>
RBTree<Key, Data>::~RBTree()
{
	Node* current = m_root;
	while(current)
	{
		if (current->left)
		{
			Node* next = current->left;
			current->left = NULL;
			current = next;
		}
		else if(current->right)
		{
			Node* next = current->right;
			current->right = NULL;
			current = next;
		}
		else
		{
			Node* next = current->parent;
			delete current;
			current = next;
		}
	}
	m_root = NULL;
}

template<typename Key, typename Data>
typename RBTree<Key, Data>::iterator RBTree<Key, Data>::insert( const value_type& value )
{
	Node* check_iterator = m_root;
	Node* insertion_parent = NULL;
	while(check_iterator)
	{
		if (check_iterator->value.first == value.first)
			return iterator(check_iterator);
		insertion_parent = check_iterator;
		check_iterator = (value.first < check_iterator->value.first) ? check_iterator->left : check_iterator->right;
	}

	Node* newNode = new Node(insertion_parent, value); 
	if (!insertion_parent)
	{
		m_root = newNode;
	}
	else
	{
		if (value.first < insertion_parent->value.first)
			insertion_parent->left = newNode;
		else
			insertion_parent->right = newNode;

	}
	correctionInsert(newNode);

	return iterator(newNode);
}

template<typename Key, typename Data>
typename RBTree<Key, Data>::iterator RBTree<Key, Data>::begin()
{
	return iterator(m_root->smallest());
}

template<typename Key, typename Data>
typename RBTree<Key, Data>::iterator RBTree<Key, Data>::end()
{
	return iterator();
}

//////////////////////////////////////////////////////////////////////////
template<typename Key, typename Data>
bool RBTree<Key, Data>::sanityCheck() const
{
	if (!m_root)
		return true;

	Node* current = m_root->smallest();
	while (current)
	{
		if (current->color == Node::RED)
		{
			if (current->left && current->left->color == Node::RED)
				return false;
			if (current->right && current->right->color == Node::RED)
				return false;
		}
		current = current->next();
	}

	return true;
}

//////////////////////////////////////////////////////////////////////////
template<typename Key, typename Data>
void RBTree<Key, Data>::rotateLeft(Node *x)
{
    Node *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != NULL)
		y->left->parent = x;

    /* establish y->parent link */
	ttAssert(y != NULL);
    if (y != NULL)
		y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    }
	else
	{
        m_root = y;
    }

    /* link x and y */
    y->left = x;
	ttAssert(x != NULL);
    if (x != NULL)
		x->parent = y;
}

template<typename Key, typename Data>
void RBTree<Key, Data>::rotateRight(Node *x)
{
    Node* y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != NULL)
		y->right->parent = x;

    /* establish y->parent link */
	ttAssert(y != NULL);
    if (y != NULL)
		y->parent = x->parent;
    if (x->parent)
	{
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    }
	else
	{
        m_root = y;
    }

    /* link x and y */
    y->right = x;

	ttAssert(x != NULL);
    if (x != NULL)
		x->parent = y;
}

template<typename Key, typename Data>
void RBTree<Key, Data>::correctionInsert( Node* node )
{
 	while(node->parent && node->parent->color == Node::RED && node->parent->parent)
 	{
		if(node->parent == node->parent->parent->left)
		{
			Node* ancle = node->parent->parent->right;
			if (ancle && ancle->color == Node::RED)
			{
				node->parent->color = Node::BLACK;
				ancle->color = Node::BLACK;
				node->parent->parent->color = Node::RED;
				node = node->parent->parent;
			}
			else
			{
				if(node == node->parent->right)
				{
					node = node->parent;
					rotateLeft(node);
				}
				node->parent->color = Node::BLACK;
				node->parent->parent->color = Node::RED;
				rotateRight(node->parent->parent);
			}
		}
		else
		{
			Node* ancle = node->parent->parent->left;
			if (ancle && ancle->color == Node::RED)
			{
				node->parent->color = Node::BLACK;
				ancle->color = Node::BLACK;
				node->parent->parent->color = Node::RED;
				node = node->parent->parent;
			}
			else
			{
				if(node == node->parent->left)
				{
					node = node->parent;
					rotateRight(node);
				}
				node->parent->color = Node::BLACK;
				node->parent->parent->color = Node::RED;
				rotateLeft(node->parent->parent);
			}
		}
 	}
	m_root->color = Node::BLACK;
}

} //namespace core
} //namespace tt